package com.atwulidun.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int[] temp = new int[arr.length];// 注意：临时数组的长度要和被排序数组的长度一样，因为最后一次归并需要用到temp的长度为arr.length
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("排序完后为：");
        System.out.println(Arrays.toString(arr));
    }

    //    // 归并排序方法
//    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
//        // 递归成立的条件
//        if (left < right) {
//            int mid = left + (right - left)/2;
//            // 左递归(若调用这次mergeSort只有两个元素，那么mid == left，则下面是对mergeSort的最后一次左递归调用)
//            mergeSort(arr, left, mid, temp);
//            // 右递归(若调用这次mergeSort只有两个元素，那么mid + 1== right，则下面是对mergeSort的最后一次右递归调用)
//            mergeSort(arr, mid + 1, right, temp);
//            // 若上面分别是对左递归和右递归的最后一次调用，则下面的merge方法便可以执行，首先将两个数合并
//            merge(arr, left, mid, right, temp);
//        }
//    }
//
//    // 合并两个有序数列的方法
//    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//        // 一、定义三个指针变量
//        int l = left;// 定义一个左指针
//        int r = mid + 1;// 定义一个右指针
//        int t = 0;// 定义一个指向temp每个位置的指针
//        // 二、对两个有序数列进行合并
//        // while循环条件是两个有序数列只有当其中一个归并完，那么才跳出循环
//        while (l <= mid && r <= right) {
//            if (arr[l] < arr[r]) {
//                temp[t] = arr[l];
//                l++;// 左指针向后移动一位
//                t++;// temp指针向后移动一位
//            } else {
//                temp[t] = arr[r];
//                r++;// 右指针向后移动一位
//                t++;// temp指针向后移动一位
//            }
//        }
//        // 三、当某个有序数列合并完后，只需要把另一个有序数列的剩下部分接着填充到temp后面即可
//        // 当右边的有序数列已经完全归并后，把左边剩下的有序数列直接全部依次赋值给temp即可
//        while (l <= mid) {
//            temp[t] = arr[l];
//            l++;// 左指针向后移动一位
//            t++;// temp指针向后移动一位
//        }
//        // 当左边的有序数列已经完全归并后，把右边剩下的有序数列直接全部依次赋值给temp即可
//        while (r <= right) {
//            temp[t] = arr[r];
//            r++;// 右指针向后移动一位
//            t++;// temp指针向后移动一位
//        }
//        // 四、在temp中排好序的有序数列要复制回原arr数组，因为上一层递归要用到这一层的有序数列，同时temp是循环多次利用的
//        // 对t进行重置
//        t = 0;
//        // 对l进行重置
//        l = left;
//        // 复制temp回arr
//        while (l <= right) {
//            arr[l] = temp[t];
//            l++;
//            t++;
//        }
//    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int l = left;
        int r = mid + 1;
        int t = 0;
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[r++];
            }
        }
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        l = left;
        t = 0;
        while (l <= right) {
            arr[l++] = temp[t++];
        }
    }

    private static void mergeSort(int[] arr, int left, int right) {
       // 控制轮数(譬如八个数，则一共要进行三轮)
        for (int i = 1; i < arr.length; i *= 2) {
            // 对每一轮中的每个小区间分别进行合并(比如第一轮就有四个小区间，每个小区间两个数)
            int step = 2 * i;
            for (int j = 0; j < arr.length; j += step) {
                // 为了防止数组元素个数为奇数个而造成的下标越界，需要使用Math.min()方法
                // 01 23 45 67 89，注意这里的9是不存在的，但是在merge方法的右边界中j + step - 1就代表9，这里就会出现数组下标越界，因此要使用Math.min()方法限制只能取arr.length-1即8
                merge(arr, j, Math.min(j + (j + step - 1 - j) / 2, arr.length - 1), Math.min(j + step - 1, arr.length - 1));
            }
        }
    }
}
